1. Field of the Invention
This invention relates to the decoding of a particular class of error-correcting codes. More specifically, the invention is an algorithm and a method that decodes parallel-concatenated convolutional codes.
2. Description of Related Art
There are several types of concatenated convolutional codes (CCC's), but the most common is parallel-concatenated convolutional codes (PCCC's) which includes so-called turbo codes introduced by Berrou, et al. (“Near Shannon limit error-correcting coding and decoding: Turbo-codes”, ICC'93, Conf Rec. pp. 1064–1070, Geneva, May 1993). The prior art of decoding of PCCC's is to use an iterative method of decoding that combines seperate estimates from each constituent subcode whereby each constituent convolutional subcode is decoded by a trellis-based maximum-a-posteriori (MAP) decoder that implements the so-called “forward-backward BCJR algorithm” to obtain the estimates (Bahl, et al.,“Optimal decoding of linear codes for minimizing symbol error rate”, IEEE Transactions on Information Theory, Vol.20, pp. 284–287, March 1974). The maximum a posteriori (MAP) algorithm, the BCJR algorithm, the forward-backward algorithm, and the APP algorithm are all the same equivalent decoding method. The same algorithm with log-likelihood ratios, also called reliabilities, replacing probabilties are called the log-MAP algorithm and the log-APP algorithm. No matter what the algorithm is called that produces the a posteriori estimates for information bits of a binary convolutional code when given channel values and a priori estimates, the MAP/BCJR algorithm requires mathematical/computational processing for mathematical functions such as multiplications, additions, divisions, logarithms, and exponentiations. The current state-of-the-art decoders for PCCC's all require a mathematical/computational processor to implement the MAP/BCJR algorithm and to combine the estimates from the seperate constituent subcodes. The computation within the MAP/BCJR algorithm can be quite extensive, so an iterative decoder for PCCC's which is computing the MAP/BCJR algorithm for each constituent subcode at each iteration can be impractical for many high-speed low-cost communication systems. There is a need for a decoding method for PCCC's that does not require a mathematical/computational processor.
Related Patent Documents
Many patent documents just refer to the mathematical/computational processor as ‘decoders’, ‘processors’, ‘calculators’, , ‘computing circuitry’, etc. (see U.S. Pat. Nos. 5,446,747; 6,023,783). Some patent documents describe attempts to streamline the decoding by using several mathematical/computational processors or by using pipelined processors or arrays of processors (see U.S. Pat. Nos. 5,487,075; 6,304,995; 6,252,917; 6,292,918; 6,128,765; 6,304,996; 6,192,501), Another two patent documents describe computing the max-log-MAP algorithm instead of the log-MAP algorithm (see U.S. Pat. Nos. 6,510,536; 6,525,680). Another patent document describes implementing the computing circuitry on a programmable logic device (see U.S. Pat. No. 6,400,290). All the current state-of-the-art decoders require at least one mathematical/computational processor for comuting some mathematical functions within the BCJR algorithm and the combining of estimates.
Another approach for a decoder of a PCCC is based on the parity-check decoders for low density parity check codes (see U.S. Pat. Nos. 6,542,559; 6,499,128). These graph-based decoders are not closely related to trellis-based MAP/BCJR decoders and they do not perform as well on the constituent convolutional codes comprising a PCCC.
Other References:
Peter C. Massey and D. Costello Jr., “Iterative Table-Lookup Decoding for a 2-state Rate=½ Turbo-like Code”, Proceedings of the 2002 IEEE International Symposium on Information Theory, Lausanne, Switzerland, pp. 340, June, 2002.
Peter C. Massey and D. Costello Jr., “New Low-Complexity Turbo-Like Codes”, Proceedings of the 2001 IEEE Information Theory Workshop, Cairns, Australia, pp. 70–72, September 2001.
L. R. Bahl, J. Cooke, F. Jelinik, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate”, IEEE Transactions on Information Theory, Vol.20, pp. 284–287, March 1974.